﻿public class Solution {
    public int MaxProfit(int[] prices)
    {
        if (prices is null || prices.Length == 0) return 0;
        
        // 不操作，第一次持有，第一次不持有，第二次持有，第二次不持有
        int[,] dp = new int[prices.Length, 5];
        dp[0, 0] = 0;
        dp[0, 1] = -prices[0];
        dp[0, 2] = 0;
        dp[0, 3] = -prices[0];
        dp[0, 4] = 0;

        for (int i = 1; i < prices.Length; i++)
        {
            dp[i, 0] = 0;
            dp[i, 1] = Math.Max(dp[i - 1, 1], dp[i - 1, 0] - prices[i]);
            dp[i, 2] = Math.Max(dp[i - 1, 2], dp[i - 1, 1] + prices[i]);
            dp[i, 3] = Math.Max(dp[i - 1, 3], dp[i - 1, 2] - prices[i]);
            dp[i, 4] = Math.Max(dp[i - 1, 4], dp[i - 1, 3] + prices[i]);
        }

        return dp[prices.Length - 1, 4];
    }

    public static void Main(string[] args)
    {
        int[] prices = [3, 3, 5, 0, 0, 3, 1, 4];
        Solution solution = new Solution();
        int res = solution.MaxProfit(prices);
        Console.WriteLine(res);
    }
}